#include <iostream>
#include <cstdio>
#include <cmath>
#define LES 19
#define LEN 20
typedef long long unsigned ll;
using namespace std;
struct number {
    ll val[LEN];
    void equal(number a) {
        for (int i=0; i<LEN; i++) {
            this->val[i]=a.val[i];
        }
    }
};
number _add(number a, number b) {
    number c;
    ll tmp=0;
    for (int i=LES; i>=0; i--) {
        c.val[i]=(a.val[i] + b.val[i] + tmp)%(ll)(pow(10,16));
        tmp=(a.val[i] + b.val[i] + tmp)/(ll)(pow(10,16));
    }
    return c;
}
int main() {
    const int num=1005;
    number a[num];
    for (int i=0; i<LES; i++) {
        a[0].val[i]=0;
        a[1].val[i]=0;
    }
    a[0].val[LES]=1; a[1].val[LES]=1;
    for (int i=2; i<num; i++) a[i].equal(_add(a[i-1], a[i-2]));
    int n,q;
    cin>>n;
    for (int i=0; i<n; i++) {
        scanf("%d", &q);
        q--;
        int j=0;
        while (a[q].val[j]==0) j++;
        printf("%lld", a[q].val[j]);
        j++;
        for (; j<LEN; j++) printf("%016lld",a[q].val[j]);
        printf("\n");
    }
    return 0;
}
